package com.lei.tree;

import java.util.Stack;

/*
判断一棵树是不是搜索二叉树

搜索二叉树:左子树节点小于它，右子树节点大于它
 */
public class SearchTree {
    public static class Node {
        int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public  boolean isSearch(Node head) {
        if (head == null) {
            return true;
        }
        int preData = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<>();
        while (head != null || !stack.isEmpty()) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                Node node = stack.pop();
                if (node.val < preData) {
                    return false;
                } else {
                    preData = node.val;
                }
                head = node.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node root = new Node(6);
        root.left = new Node(3);
        root.left.left = new Node(1);
        root.left.right = new Node(4);
        root.right = new Node(8);
        root.right.left = new Node(7);
        root.right.right = new Node(10);
        SearchTree searchTree = new SearchTree();

        System.out.println(searchTree.isSearch(root));
    }
}
